package leetcode.practice;

/**
 * 234. 回文链表
 */
public class IsPalindromeLinkedList {


    /**
     * 翻转后半截 再比较 1 空间复杂度的
     *
     * @param head
     * @return
     */
    public Boolean ism(ListNode head) {
        if (head == null) {
            return false;
        }

        // 计算长度
        int length = 0;
        ListNode cur = head;
        while (cur != null) {
            length++;
            cur = cur.next;
        }

        // a b c d  e f
        // length = 4
        // 中间切分
        int leftLength = length % 2 == 1 ? length / 2 + 1 : length / 2;
        ListNode leftEnd = head;
        while (leftLength > 1) {
            leftEnd = leftEnd.next;
            leftLength--;
        }

        ListNode right = leftEnd.next;
        leftEnd.next = null;

        // 翻转
        ListNode pre = null;
        ListNode next = null;
        while (right != null) {
            next = right.next;
            right.next = pre;
            pre = right;
            right = next;
        }
        right = pre;

        // 对比
        while (right != null && head != null) {
            if (right.val == head.val) {
                head = head.next;
                right = right.next;
            } else {
                return false;
            }
        }

        return true;
    }

    class ListNode {
        int val;
        ListNode next;
    }
}

